#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define BORRA_BUFFER    while(getchar()!= '\n');
#define MAX_MSG_LEN	500
#define MAX_KEY_LEN	20
#define MAX_FREQ_LEN	20
#define EXTR_FREQ	3
#define HIGH_LIM	3
#define LOW_LIM		2
#define CANT_FREQ	5

#define EXTR_FREQPART	3
#define HIGH_LIMPART	1
#define LOW_LIMPART		2



int key_length (char * enc_msg);
int getLine (char * line, int linelen, FILE * stream);
int getPos(char letra, char * arr);
void count (char letra, int * arr, int i, char * msg);
int caesar (char * msg_enc, char * msg_des, int key_len, int offset, int freq_sel);
int isPossible (char * msg);
void Wrecur (char ** parts, int key_len, int last, char ** des_arr, int msg_len);
void recur (char ** parts, int * high, int key_len, int last, char ** des_arr, int msg_len, int *cant, char *single);
int join(char * des, char * single, int key_len, int offset, int msg_len);
double * mcd_vigenere(int numbers[], int dim);
int method (char * msg_enc);

int
main (void)
{
	char msg_enc[MAX_MSG_LEN] = {0};
	char msg_des[MAX_MSG_LEN] = {0};
	int key_len, msg_len;
	char * div[10];
	int i, j, k;
	char ** des_arr;
	int tot_msgs;

	printf("Ingrese el texto encriptado con metodo Vigenere: ");
	getLine (msg_enc, MAX_MSG_LEN, stdin);
	msg_len = strlen(msg_enc);

	while(1){

		key_len = method (msg_enc);


		for (i = 0; i < key_len; i++)
		{
			div[i] = (char*) calloc(((msg_len / key_len) + 1), sizeof(char));

			for (j = 0, k = 0; j < msg_len - i; j += key_len, k++)
			{
				div[i][k] = msg_enc[j + i];

			}
			printf("PART %d: %s\n", i+1, div[i]);
		}

		tot_msgs = 1;
		for (i = 0; i < key_len; i++)
		{
			tot_msgs *= CANT_FREQ;
		}

		des_arr = (char **) calloc (tot_msgs, sizeof(char *));

		Wrecur (div, key_len, key_len - 1, des_arr, msg_len);

	/*	for (i = 0; i < key_len; i++)
		{
			caesar(div[i], msg_des, key_len, i);
		}
	*/

		for (i = 0; i < tot_msgs; i++)
		{
			if (isPossible (des_arr[i]))
				printf("MSG: %s\n", des_arr[i]);
	//		else
	//			printf ("Baja coincidencia\n");
		}


		for (i = 0; i < key_len; i++)
		{
			free(div[i]);
		}
	}
	/*for (i = 0; i < tot_msgs; i++)
	{
		free(des_arr[i]);
	}
	free(des_arr);
	*/

	return 0;
}

int key_length (char * enc_msg)
{
	char aux[4] = {0};
	int dists[100] = {0};
	int msg_len;
	int i, k;
	int j = 0, cant = 0;
	int rec_key = 0;

	msg_len = strlen(enc_msg);

	for (k = 0; k < msg_len - 3; k++)
	{
		for (i = k + 3; i < msg_len; i++)
		{
			strncpy(aux, enc_msg + k, 3);

			if (strncmp(aux, enc_msg + i, 3) == 0)
			{
				dists[j++] = i - k;
				cant++;
			}
		}
	}

	printf("DISTANCIAS:\n");
	for (i = 0; i < cant; i++)
	{
		printf("%d | ", dists[i]);
	}
	printf("\n");

	double * prob_keys;

	prob_keys = mcd_vigenere(dists, cant);
	for(i = 0; i<cant; i++){
		if(prob_keys[i] > 0.50)
			printf("Clave recomendada: %.2g - %d\n", prob_keys[i], i+1);

	}
	return cant;

}

int
getLine (char * line, int linelen, FILE * stream)
{
    int i=0, c;
    for (i=0;i<linelen;i++)
        line[i] = 0;
    i=0;
    while(i<linelen){
        c=fgetc(stream);
        if(c==EOF)
                return -1;

        if(c=='\n')
                return 1;

        line[i]=c;
        i++;
    }

    if (i >= linelen)
        {
            BORRA_BUFFER;
        return 0;
        }
    return 0;
}
/*
void
caesarW (char * msg_enc, char ** msg_des, int key_len, int offset)
{
	int i;
	int msg_len;

	msg_len = strlen(msg_enc);

	for (i = 0; i < CANT_FREQ; i++)
	{
		msg_des[i] = (char *) calloc (msg_len, sizeof(char));
		caesar (msg_enc, msg_des[i], key_len, offset);
	}

	return;

}
*/

int
caesar (char * msg_enc, char * msg_des, int key_len, int offset, int freq_sel)
{
	int i = 0, j, max = 0, k;
	char * freq = "EAOSRNIDLCTUMPBGVYQHFZJXWK";
	char * alf = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	int key;
	int * arr;
	char * des;
	int * pos;
	int flag = 1, alf_len, msg_len;
//	int freq_sel;
	char cfreq_sel[MAX_FREQ_LEN] = {0};

/*	printf("Ingrese el indice de letra con mayor freq: ");
	getLine (cfreq_sel, MAX_FREQ_LEN, stdin);
	sscanf (cfreq_sel, "%d", &freq_sel);
*/
	alf_len = strlen(alf);
	msg_len = strlen(msg_enc);

	arr = (int *) calloc (alf_len, sizeof(int));

	des = (char *) calloc ( msg_len, sizeof(char));

	pos = (int *) calloc (msg_len , sizeof(int));


	for (i = 0; i < msg_len; i++)
	{
		flag = 1;
		for (j = 0; (j < alf_len && flag); j++)
		{
			if (msg_enc[i] == alf[j])
			{
				pos[i] = j;
				flag = 0;
			}
		}
	}

	for(i = 0; i < alf_len; i++)
	{
		count(alf[i], arr, i, msg_enc);
	}

	printf("\n%s\n", alf);

	for (i = 0; i < alf_len; i++)
	{
		printf("%d", arr[i]);
	}
	printf("\n");

	for (j = 0; j < alf_len; j++)
	{
		if (arr[max] < arr[j])
			max = j;
	}


	if ((key = max - getPos (freq[freq_sel], alf)) < 0)
		key += alf_len;

	int neg;
	for (j = 0; j < msg_len; j++)
	{
		if ((neg = (pos[j] - key)) < 0)
			des[j] = alf[alf_len + neg];
		else
			des[j] = alf[pos[j] - key];
	}
	des[msg_len] = 0;

//	printf ("MESSAGE:\n    %s\n", des);

	strncpy(msg_des, des, msg_len);

	if (isPossiblePart(msg_des))
		return 1;
	return 0;
}

void
count (char letra, int * arr, int i, char * msg)
{
	int tot;
	int cant = 0;
	int j = 0;

	tot = strlen(msg);
	while (j < tot)
	{
		if (msg[j++] == letra)
			cant++;
	}
	arr[i] = cant;
}

int getPos(char letra, char * arr)
{
	int cant;
	int i;

	cant = strlen(arr);
	for(i = 0; i < cant; i++)
	{
		if (letra == arr[i])
			return i;
	}
	return -1;
}

int isPossible (char * msg)
{
	char * freq = "EAOSRNIDLCTUMPBGVYQHFZJXWK";
	int msg_len, alf_len;
	int * reps;
	float * perc;
	int i;

	alf_len = strlen(freq);
	msg_len = strlen(msg);

	if ((reps = (int *) malloc(alf_len * sizeof(int))) == NULL)
	{
		printf("Malloc Error\n");
		exit (1);
	}
	if ((perc = (float *) malloc(alf_len * sizeof(float))) == NULL)
	{
		printf("Malloc Error\n");
		exit (1);
	}

	for (i = 0; i < alf_len; i++)
	{
		count (freq[i], reps, i, msg);
		perc[i] = (float)((int)(((float)(reps[i] * 100) / msg_len) * 100)) / 100;
	}

	for (i = 0; i < EXTR_FREQ; i++)
	{
		if (perc[i] < HIGH_LIM)
		{
			free(reps);
			free(perc);
			return 0;
		}
	}

	for (i = alf_len - 1; i > ((alf_len - EXTR_FREQ) - 1); i--)
	{
		if (perc[i] > LOW_LIM)
		{
			free(reps);
			free(perc);
			return 0;
		}
	}
	free(reps);
	free(perc);
	return 1;
}

void Wrecur (char ** parts, int key_len, int last, char ** des_arr, int msg_len)
{
	int * high;
	int cant = 0, i;
	int tot_des;
	char *single;
	int part_len;

	part_len = (msg_len/key_len) + 1;
	single = (char*) calloc (part_len, sizeof(char));

	tot_des = 1;
	for (i = 0; i < key_len; i++)
	{
		tot_des *= CANT_FREQ;
	}

	printf("TOTAL: %d", tot_des);

	high = (int *) calloc (key_len, sizeof(int));

	for (i = 0; i < tot_des; i++)
	{
		des_arr[i] = (char *) calloc (msg_len, sizeof(char));
	}

	recur (parts, high, key_len, last, des_arr, msg_len, &cant, single);
	return;
}

void recur (char ** parts, int * high, int key_len, int last, char ** des_arr, int msg_len, int *cant, char *single)
{
	int i, j;
	int flag = 0;


	if(last == 0)
	{
		for (i = 0; i < CANT_FREQ; i++)
		{
			high[key_len - 1] = i;
			flag = 0;
//			des_arr[i] = (char *) calloc (msg_len, sizeof(char));
			/* validar si una parte no cumple las frecuencias y en ese caso cambiar */
			for (j = 0; j < key_len && !flag; j++)
			{
				if (caesar(parts[j], single, key_len, j, high[j]))
					join (des_arr[*cant], single, key_len, j, msg_len);
				else
					flag = 1;
			}
			if (!flag)
			{
				(*cant)++;
				printf ("CANT: %d\n", *cant);
			}
		}

		return ;
	}

	for (i = 0; i < CANT_FREQ; i++)
	{
		high[(key_len - 1) - last] = i;
		recur (parts, high, key_len, last - 1, des_arr, msg_len, cant, single);
	}
	return ;
}

int join(char * des, char * single, int key_len, int offset, int msg_len)
{
	int i, k;

	for (i = 0, k = 0; i < msg_len; i++, k += key_len)
	{
		des[k + offset] = single[i];
	}
	return 1;
}

int isPossiblePart (char * msg)
{
	char * freq = "EAOSRNIDLCTUMPBGVYQHFZJXWK";
	int msg_len, alf_len;
	int * reps;
	float * perc;
	int i;

	alf_len = strlen(freq);
	msg_len = strlen(msg);

	if ((reps = (int *) malloc(alf_len * sizeof(int))) == NULL)
	{
		printf("Malloc Error\n");
		exit (1);
	}
	if ((perc = (float *) malloc(alf_len * sizeof(float))) == NULL)
	{
		printf("Malloc Error\n");
		exit (1);
	}

	for (i = 0; i < alf_len; i++)
	{
		count (freq[i], reps, i, msg);
		perc[i] = (float)((int)(((float)(reps[i] * 100) / msg_len) * 100)) / 100;
	}

	for (i = 0; i < EXTR_FREQPART; i++)
	{
		if (perc[i] < HIGH_LIMPART)
		{
			free(reps);
			free(perc);
			return 0;
		}
	}

	for (i = alf_len - 1; i > ((alf_len - EXTR_FREQPART) - 1); i--)
	{
		if (perc[i] > LOW_LIMPART)
		{
			free(reps);
			free(perc);
			return 0;
		}
	}
	free(reps);
	free(perc);
	return 1;
}

double *
mcd_vigenere(int numbers[], int dim)
{
	double * Divisores;
	int i, Max = 0;
	int CurrDiv = 10;

	Divisores = calloc(10, sizeof(double));
	if( Divisores == NULL )
		return NULL;

	for(i = 0; i < dim; i++){
		for(CurrDiv = 10; CurrDiv > 1; CurrDiv--){
			if(numbers[i] % CurrDiv == 0)
			{
				Divisores[CurrDiv - 1] = Divisores[CurrDiv - 1] + (double) 1/ (double) dim;
				if(Divisores[CurrDiv - 1] > Max)
					Max = Divisores[CurrDiv - 1];
			}

		}

	}

	return Divisores;

}

int method (char * msg_enc)
{
	int i = 0, j, max = 0;
	char * freq = "EAOSRNIDLCTUMPBGVYQHFZJXWK.";
	char * alf = "ABCDEFGHIJKLMN.OPQRSTUVWXYZ";
	int key;
	int * arr;
	int * pos;
	int flag = 1, alf_len, msg_len;
	char ckey_len[MAX_KEY_LEN] = {0};
	int key_len;


	alf_len = strlen(alf);
	msg_len = strlen(msg_enc);

	arr = (int *) calloc (alf_len, sizeof(int));
	pos = (int *) calloc (msg_len , sizeof(int));


	for (i = 0; i < msg_len; i++)
	{
		flag = 1;
		for (j = 0; (j < alf_len && flag); j++)
		{
			if (msg_enc[i] == alf[j])
			{
				pos[i] = j;
				flag = 0;
			}
		}
	}

	for(i = 0; i < alf_len; i++)
	{
		count(alf[i], arr, i, msg_enc);
	}


	for (j = 0; j < alf_len; j++)
	{
		if (arr[max] < arr[j])
			max = j;
	}

	if (alf[max] == freq[0] || alf[max] == freq[1] || alf[max] == freq[2])
	{
		printf ("\nTRANSPOSICION!!\n\n");
		/*TODO: Llamada trans */
	}

	else if (key_length (msg_enc) > 1)
	{
		printf("\nVIGENERE!\n");
		printf("Ingrese la longitud de la clave: ");
		getLine (ckey_len, MAX_KEY_LEN, stdin);
		sscanf (ckey_len, "%d", &key_len);
	}
	else
	{
		key_len = 1;
		printf("\nCAESAR!\n");
	}

	return key_len;
}
